// 动态规划 - 核心 5 步：
// 1. 确定状态表示 - 根据 题目要求，经验(以 i,j 位置为结尾/开始......)，发现重复子问题 确定状态表示
// 2. 推导状态转移方程: dp[i] = ?
//    用 之前的状态 或者 之后的状态 推导当前的状态（根据最近一步划分问题）
// 3. 初始化：保证填表时不越界，结合多开数组的技巧
// 4. 确定填表顺序：填写当前状态值的时候，所需状态的值已经计算过了
// 5. 返回值：结合题目要求 + 状态表示

// 技巧：
// 01 背包问题：使用滚动数组进行优化，删除横坐标，从右往左填表
// 完全背包问题：使用滚动数组进行优化，删除横坐标，从左往右填表

// 例题 10:
// 集团里有 n 名员工，他们可以完成各种各样的工作创造利润。
//
//        第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。
//
//        工作的任何至少产生 minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。
//
//        有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。
//
//        示例 1：
//
//        输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3]
//        输出：2
//        解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，或仅完成工作 1 。
//        总的来说，有两种计划。
//        示例 2：
//
//        输入：n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
//        输出：7
//        解释：至少产生 5 的利润，只要完成其中一种工作就行，所以该集团可以完成任何工作。
//        有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。
//
//
//        提示：
//
//        1 <= n <= 100
//        0 <= minProfit <= 100
//        1 <= group.length <= 100
//        1 <= group[i] <= 100
//        profit.length == group.length
//        0 <= profit[i] <= 100

// 解题思路:
// dp[i][j][k] 表示 [0, i] 区间内 最小利润不小于 j, 需要的员工个数不超过 k 的盈利计划的种数
// 初始化：dp[0][0][k] = 1, 0 <= k <= n
// 根据最后一个位置的字符串分情况讨论：
// 不选最后一个字符串：dp[i][j][k] = dp[i - 1][j][k]
// 选最后一个字符串：dp[i][j][k] = dp[i - 1][j - profit[i]][k - group[i]]
// 取两者的和
// 注意:
// 当 j - profit[i] < 0 也是符合要求的结果，因此需要做一下处理，
// 当 j - profit[i] < 0, 需要找一下 dp[i - 1][0][k - group[i]]，因为实际不会存在负数下标，利润 >= 0都是符合要求的结果

public class ProfitableSchemes {
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int m = group.length;
        int[][][] dp = new int[m + 1][minProfit + 1][n + 1];

        for(int k = 0; k <= n; k++)
        {
            dp[0][0][k] = 1;
        }

        for(int i = 1; i <= m; i++){
            for(int j = 0; j <= minProfit; j++){
                for(int k = 0; k <= n; k++){
                    dp[i][j][k] = dp[i - 1][j][k];
                    if(k >= group[i - 1]){
                        dp[i][j][k] += (dp[i - 1][Math.max(0, j - profit[i - 1])][k - group[i - 1]]);
                    }
                    dp[i][j][k] %= (1e9+7);
                }
            }
        }
        return dp[m][minProfit][n];
    }
}
